package com.explorati.LeetCode003.lengthOfLongestSubstring;

import java.util.HashSet;
import java.util.Set;

/**
 * 暴力解法 时间复杂度：O(n^3)
 * 
 * @author explorati
 *
 */
class Solution {
	public int lengthOfLongestSubstring(String s) {
		int n = s.length();
		// 记录最长无重复字符的字符串的长度
		int ans = 0;
		// 将字符串从第一个字母一个一个向后遍历完所有O(n^2)
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j <= n; j++) {
				if (isUniqueStr(s, i, j)) {
					// if (ans < j - i) {
					// ans = j - i;
					// }
					// 判断ans和现在这个没有重复元素的字符串的长度谁更长
					ans = Math.max(ans, j - i);
				}
			}
		}
		return ans;
	}

	// 判断是否是无重复字符的字符串
	public static boolean isUniqueStr(String s, int i, int j) {
		String str = s.substring(i, j);
		Set<Character> set = new HashSet<Character>();
		for (int k = 0; k < str.length(); k++) {
			if (set.contains(str.charAt(k))) {
				return false;
			}
			set.add(str.charAt(k));
		}
		return true;
	}

	public static void main(String[] args) {
		String s = "abcabca";
		Solution solution = new Solution();
		System.out.println("字符串无重复字母的最大长度为：" + solution.lengthOfLongestSubstring(s));
	}
}
